//森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。 
//
// 返回森林中兔子的最少数量。 
//
// 
//示例:
//输入: answers = [1, 1, 2]
//输出: 5
//解释:
//两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
//之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
//设回答了 "2" 的兔子为蓝色。
//此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
//因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。
//
//输入: answers = [10, 10, 10]
//输出: 11
//
//输入: answers = []
//输出: 0
// 
//
// 说明: 
//
// 
// answers 的长度最大为1000。 
// answers[i] 是在 [0, 999] 范围内的整数。 
// 
// Related Topics 贪心 哈希表 数学 
// 👍 199 👎 0

  
package com.zwy.leetcode.editor.cn;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author zwy 
 */
public class RabbitsInForest{
    public static void main(String[] args) {
        Solution solution = new RabbitsInForest().new Solution();
        int []answers = {0,1,0,2,0,1,0,2,1,1};
        int i = solution.numRabbits(answers);
        System.out.println(i);
    }
     
/**
 *时间复杂度为:
 * @author zwy 
 */ 
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numRabbits(int[] answers) {
        Map<Integer,Integer> map=new HashMap<>();
        int count=0;
        for (int i = 0; i < answers.length; i++) {
            if(map.containsKey(answers[i])){
                map.put(answers[i],map.get(answers[i])+1);
            }
            else {
                map.put(answers[i],1);
            }
        }
        Set<Integer> set = map.keySet();
        for (Integer integer : set) {
            if(integer==0){
                count+=map.get(integer);
            }
            else if(integer+1>=map.get(integer)){
                count=count+integer+1;
            }
            else {
                count+=getN(integer,map.get(integer));
            }
        }
        return count;
    }
    public int getN(int num,int count){
        int res=0;
        while (num+1<=count){
            count-=num+1;
            res+=num+1;
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}